package com.lun.swordtowardoffer2.c06;

public class MaximalRectangle {

	private static final LargestRectangleArea lra = new LargestRectangleArea();
	
	public int maximalRectangle(char[][] matrix) {
		if(matrix.length == 0 || matrix[0].length == 0)
			return 0;
		int maxArea = 0;
		int[] heights = new int[matrix[0].length];
		for(char[] row : matrix) {
			for(int i = 0; i < row.length; i++) {
				heights[i] = row[i] == '0' ? 0 : heights[i] + 1;
			}
			maxArea = Math.max(maxArea, lra.largestRectangleArea3(heights));
		}
		return maxArea;
	}
	
}
